import java.util.ArrayList;
import java.util.List;

/**
 * @author: 最帅的的乐乐
 * @date: 2025-02-20 13:46 星期四
 * @motto the harder, the luckier。
 */

public class _39_CombinationSum {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        back(candidates, target, res, tmp, 0);
        return res;
    }

    public void back(int[] candidates, int target, List<List<Integer>> res, List<Integer> tmp, int cur) {
        if (target == 0) {
            res.add(new ArrayList<>(tmp)); // 目标值为0时，保存当前组合
            return;
        }

        for (int i = cur; i < candidates.length; i++) {
            if (candidates[i] <= target) {
                tmp.add(candidates[i]); // 加入当前候选值
                back(candidates, target - candidates[i], res, tmp, i); // 递归调用，允许重复使用同一个数字
                tmp.remove(tmp.size() - 1); // 回溯，移除最后添加的元素
            }
        }
    }

    public static void main(String[] args) {
        _39_CombinationSum solution = new _39_CombinationSum();

        // 示例输入
        int[] candidates = {2, 3, 6, 7};
        int target = 7;

        // 获取所有可能的组合
        List<List<Integer>> result = solution.combinationSum(candidates, target);

        // 输出结果
        System.out.println("Possible combinations:");
        for (List<Integer> combination : result) {
            System.out.println(combination);
        }
    }
}
